# -*- coding: utf-8 -*-
"""
动态规划算法解决0-1背包问题:对于一组不可分割、不同重量的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，
背包中物品总重量的最大值是多少？
"""
from typing import List, Tuple


def knapsack(weights: List[int], max_weight: int):
    """
    0-1背包问题：
    :param weights: 物品的重量
    :param max_weight: 背包能承受的最大重量
    :return: 在满足背包最大重量限制的前提下，放入背包物品总重量的最大值
    """
    num_items = len(weights)
    status = [[False] * (max_weight + 1) for i in range(num_items)]
    status[0][0] = True  # 第一行的数据需要特殊处理，可以利用哨兵优化
    if weights[0] <= max_weight:
        status[0][weights[0]] = True

    for i in range(1, num_items):
        for j in range(max_weight + 1):
            if status[i - 1][j]:
                status[i][j] = status[i - 1][j]  # 不把第i个物品放入背包
                if j + weights[i] <= max_weight:
                    status[i][j + weights[i]] = True  # 把第i个物品放入背包

    for i in range(max_weight, -1, -1):
        if status[-1][i]:
            return i


def knapsack1(weights: List[int], max_weight: int) -> int:
    """
    0-1背包问题：使用一维数组实现
    :param weights: 物品的重量
    :param max_weight: 背包能承受的最大重量
    :return: 在满足背包最大重量限制的前提下，放入背包物品总重量的最大值
    """
    num_items = len(weights)
    status = [False] * (max_weight + 1)  # 记录每个阶段的状态值。
    status[0] = True

    if weights[0] <= max_weight:  # 先处理动态规划的第一个阶段
        status[weights[0]] = True

    for i in range(1, num_items):  # i 表示动态规划的阶段
        for j in range(max_weight - weights[i], -1, -1):  # 将第i个物品放入背包
            if status[j]:
                status[j + weights[i]] = True
    print(status)
    for i in range(max_weight, -1, -1):
        if status[i]:
            return i

    return 0


def knapsack_with_max_value(items_info: List[Tuple[int, int]], max_weight: int) -> int:
    """
    0-1背包问题：计算能装进背包的物品组合的最大价值
    :param items_info: 物品信息，tuple的值分别为物品的重量和物品的价值
    :param max_weight: 背包能承受的最大重量
    :return: 能装进背包的物品组合的最大价值
    """
    num_items = len(items_info)
    status = [0] * (max_weight+1)

    if items_info[0][0] <= max_weight:
        status[items_info[0][0]] = items_info[0][1]

    for i in range(1,num_items):    # i 表示动态规划的阶段
        for j in range(max_weight - items_info[i][0], -1, -1):  # 将第i个物品放入背包
            if status[j] > 0:
                status[j + items_info[i][0]] = max(status[j + items_info[i][0]], status[j] + items_info[i][1])
    print(status)
    return max(status)


if __name__ == "__main__":
    test_weights = [10, 2, 1, 1, 3, 5, 6, 7]
    test_max_weight = 23
    test_item_list = [(1,2),(2,4),(3,2)]
    print(knapsack(test_weights, test_max_weight))
    print(knapsack1(test_weights, test_max_weight))
    print(knapsack_with_max_value(test_item_list,4))
